package sort;

import org.junit.jupiter.api.Test;
import java.util.Arrays;
import java.util.Random;

/**
 * 快速排序：荷兰国旗，二分 + 递归
 */
public class TestQuickSort {

    @Test
    public void test01() {
        // 1. 准备样本
        int[] arr = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            arr[i] = random.nextInt(100);
        }
        System.out.println(Arrays.toString(arr));

        // 2. 快速排序
        quickSort(arr, 0, 9);

        // 3. 验收成果
        System.out.println(Arrays.toString(arr));

    }

    public void quickSort(int[] arr, int L, int R) {
        // 基本情形
        if (L >= R) {
            return;
        }

        // 递归情形
        Random random = new Random();
        int pivot = arr[L + random.nextInt(R - L + 1)];  // 划分值
        int small = L - 1;  // 小于区边界位置
        int big = R + 1;  // 大于区边界位置
        int i = L;  // 待定区遍历指针

        while(i < big) {  // 当 i 和 big 未遭遇
            if (arr[i] < pivot) {  // 如果 arr[i]小于划分值
                swap(arr, i++, ++small);
            } else if (arr[i] == pivot) {  // 如果 arr[i]等于划分值
                i++;
            } else {
                swap(arr, i, --big);  // 如果 arr[i]大于划分值
            }
        }

        quickSort(arr, L, small);  // 小于区递归
        quickSort(arr, big, R);  // 大于区递归
    }


    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
